/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
// 深度优先超时
var combinationSum4 = function (nums, target) {
    let res = 0
    const dfs = function (target) {
        if(target === 0) {
            res++
            return
        }
        if(target < 0) return
        for(let i = 0; i < nums.length; i++) {
            dfs(target - nums[i])
        }
    }
    dfs(target)
    return res
};
// 不能用深度优先搜索，用动态规划，爬楼梯的方式去思考。引入记忆化搜索的方案
// nums为爬楼梯能走的台阶数，那么爬target个楼梯有多少种方案？
var combinationSum4 = function (nums, target) {
    // 记忆化数组初始化的原则：不能和初始状态相等，比如dfs(0)是0，如果记忆化数组也初始化为0
    // 那么无法区分这个部分有没有被搜索过
    const memo = new Array(target + 1).fill(-1)
    const dfs = function(target) {
        // 楼梯爬完，有一种方案
        if(target === 0) return 1
        if(memo[target] !== -1) return memo[target] // 之前已经搜索过
        let res = 0
        for(let step of nums) {
            if(step <= target) {
                res += dfs(target - step)
            }
        }
        // 记录搜索结果
        memo[target] = res
        return res
    }
    return dfs(target)
};
console.log(combinationSum4([1, 2, 3], 32));
// console.log(combinationSum4([9], 3));
// console.log(combinationSum4([9], 3));